abc152 f
abc152_f
N=50
木の2点を結ぶパスに1つ以上黒があることが条件
「パスがすべて白」
これは求めやすい、パスの長さをxとしたら2^(N-x)ぐらい
一つの制約に注目して、それが違反してる場合の数は簡単に求まる。制約は複数ある、同時に満たされるケースがダブルカウントされてる→ 包除原理だね 制約は20個ある。2^20はきわどい。DPするのかな？
複数の制約のパスが重なることある？当然ある
これは厄介だな？
複数のパスの集合にパスを付け加えた場合の「重なる辺の数」を高速に得ることが必要？
公式解説
包除原理までOK
複数のパスの重なり合いに関して「最小共通祖先を求めて木上で累積和」らしい、よくわからん 2^20の全パターンでO(N+M)で数えるらしい
別解
辺が高々50なのでint64に収まる
パスをビットで表現しておけばORで重ね合わせを計算できる